package leetcode.Hot100;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @author Cheng Jun
 * Description: 给你一个字符串 s 和一个字符串列表 wordDict 作为字典，判定 s 是否可以由空格拆分为一个或多个在字典中出现的单词。
 * <p>
 * 说明：拆分时可以重复使用字典中的单词。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/word-break
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/11/18 10:52
 */
public class wordBreak {

    static HashSet<String> wordDictSet;
    static boolean canSplit = false;

    public static void main(String[] args) {
        // 如果使用递归，下面的例子所需的递归次数呈现 指数爆炸式 增长，时间复杂度太高 10^n (10 取的是  wordDict.add("aaaaaaaaaa"))， n 表示 s.length
        List<String> wordDict = new ArrayList<>();
        wordDict.add("a");
        wordDict.add("aa");
        wordDict.add("aaa");
        wordDict.add("aaaa");
        wordDict.add("aaaaa");
        wordDict.add("aaaaaa");
        wordDict.add("aaaaaaa");
        wordDict.add("aaaaaaaa");
        wordDict.add("aaaaaaaaa");
        wordDict.add("aaaaaaaaaa");
        System.out.println(wordBreak("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab", wordDict));
    }

    // 先把 wordDict 转成 wordDictSet
    // s 开头的字母很重要，假设s 开头的字符为未知字符 x
    // 查一下 wordDictSet 有哪些以 x 开头的 word，每个 word 都是一种可能
    // 然后截取掉 s 截取掉 word ，又回到了 该问题。直到找不到 s迭代到最后 的 word
    static boolean wordBreak(String s, List<String> wordDict) {
        // 判断 s 中是否 有字符 不存在于 WordDict中
        HashSet<Character> wordDictXSet = new HashSet<>();
        for (String word : wordDict) {
            for (char c : word.toCharArray()) {
                wordDictXSet.add(c);
            }
        }
        for (char c : s.toCharArray()) {
            if (!wordDictXSet.contains(c)) {
                return false;
            }
        }
        wordDictSet = new HashSet<>(wordDict);
        findWord(s);
        return canSplit;
    }

    // 递归查询
    static void findWord(String subString) {
        if (wordDictSet.contains(subString)) {
            canSplit = true;
        } else {
            String x = String.valueOf(subString.charAt(0));
            List<String> xWordList = wordDictSet.stream().filter(word -> word.startsWith(x)).collect(Collectors.toList());
            for (String xWord : xWordList) {
                // 如果字符串 以 xWord 开头就可以截取后进行递归
                if (subString.startsWith(xWord)) {
                    findWord(subString.substring(xWord.length()));
                }
            }
        }
    }


}
